package org.kk.stack;

import java.util.Stack;

/**
 * 两个栈实现队列
 * @author kk
 * @Date 2021/1/21
 */
public class DoubleSQueue {
    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> stack2 = new Stack<>();

    /**
     * 入栈
     * 时间空间复杂度为 O(1)
     */
    public void push(int node){
        stack1.push(node);
    }

    /**
     * 出战
     * 时间复杂度 空间复杂度 均为 O(1)
     */
    public int pop() throws Exception{
        if(stack1.isEmpty() && stack2.isEmpty()){
            throw  new Exception("栈为空");
        }
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}
